package com.cqs.leetcode.math;

/**
 * @author lixiaowen
 * @create 2019-12-14
 */
public class UglyNumberII264 {



    public int nthUglyNumber(int n) {
        int[] uglyNumbers = new int[1690];
        int i = 0, j = 0, k = 0;
        uglyNumbers[0] = 1;
        int cnt = 0;
        while (++cnt < n) {
            int next0 = uglyNumbers[i] * 2;
            int next1 = uglyNumbers[j] * 3;
            int next2 = uglyNumbers[k] * 5;
            int min = next0;
            if (next1 < min) {
                min = next1;
            }
            if (next2 < min) {
                min = next2;
            }
            uglyNumbers[cnt] = min;
            if (min == next0) {
                i++;
            }
            if (min == next1) {
                j++;
            }
            if (min == next2){
                k++;
            }
        }
        return uglyNumbers[n - 1];
    }


    /***
     * 超时
     * @param n
     * @return
     */
    public int nthUglyNumber0(int n) {
        int result = 0;
        while (n > 0) {
            if (isUgly(++result)) {
                n--;
            }
        }
        return result;
    }

    public boolean isUgly(int n) {
        while (n % 2 == 0 && n != 0) {
            n /= 2;
        }
        while (n % 3 == 0 && n != 0) {
            n /= 3;
        }
        while (n % 5 == 0 && n != 0) {
            n /= 5;
        }
        return n == 1;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int size = 1690;
        int result = new UglyNumberII264().nthUglyNumber(size);
        System.out.println("result:" + result);
        System.out.println((System.currentTimeMillis() - start) / 1000 + " 秒");
    }
}
